/*
题目: 找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）

https://leetcode.cn/problems/find-all-anagrams-in-a-string
 */
public class FindAnagrams {
    // 此题包含基础版 和 优化版
    public List<Integer> findAnagrams(String s, String p) {
        // 滑动窗口优化 -- 用 diff 记录不满足的 字母 种数 -- 种类计数
        List<Integer> src = new ArrayList<> ();
        int slen = s.length(), plen = p.length();
        if (slen < plen)    return src;

        int diff = 0;
        // 使用一个数组来统计两者的差异即可
        int[] cnt = new int[26];
        for (int i = 0; i < plen; i ++) {
            cnt[s.charAt(i) - 'a'] ++;
            cnt[p.charAt(i) - 'a'] --;
        }
        for (int i = 0; i < 26; i ++) {
            if (cnt[i] != 0) {
                diff ++;
            }
        }

        if (diff == 0)  src.add(0);

        // 前面情况已经判断过了, 一进循环窗口就往右移, 并且判断窗口移动后的情况
        for (int i = 0; i < slen - plen; i ++) {
            // 分别考虑左边界和右边界 移动后 diff 的变化情况
            if (cnt[s.charAt(i) - 'a'] == 1) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从不同变得相同
                diff --;
            } else if (cnt[s.charAt(i) - 'a'] == 0) {  // 窗口中字母 s[i] 的数量与字符串 p 中的数量从相同变得不同
                diff ++;
            }
            cnt[s.charAt(i) - 'a'] --;

            if (cnt[s.charAt(i + plen) - 'a'] == -1) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从不同变得相同
                diff --;
            } else if (cnt[s.charAt(i + plen) - 'a'] == 0) {  // 窗口中字母 s[i+pLen] 的数量与字符串 p 中的数量从相同变得不同
                diff ++;
            }
            cnt[s.charAt(i + plen) - 'a'] ++;

            if (diff == 0) {
                src.add(i + 1);
            }
        }

        return src;
    }

    // 滑动窗口 ---- 基础版
    public List<Integer> findAnagramsBase(String s, String p) {
        // 滑动窗口
        List<Integer> src = new ArrayList<> ();
        int m = s.length(), n = p.length();
        if (m < n)  return src;

        // 判断每个窗口中  的 [相等情况], 先填满窗口
        int[] sCnt = new int[26];
        int[] pCnt = new int[26];
        for (int i = 0; i < n; i ++) {
            sCnt[s.charAt(i) - 'a'] ++;
            pCnt[p.charAt(i) - 'a'] ++;
        }

        if (Arrays.equals(pCnt, sCnt)) {
            src.add(0);
        }

        // 窗口为 [i + 1, i + n]
        for (int i = 0; i < m - n; i ++) {
            sCnt[s.charAt(i) - 'a'] --;
            sCnt[s.charAt(i + n) - 'a'] ++;

            // 至此 窗口为 [i + 1, i + n]
            if (Arrays.equals(sCnt, pCnt)) {
                src.add(i + 1);
            }
        }

        return src;
    }
}
